# KMP 字符串匹配算法
# http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
# 构建前缀表
def prefix_table(needle, prefix, n):
    prefix[0] = 0
    len = 0
    i = 1
    while(i < n):
        if (needle[i] == needle[len]):
            len += 1
            prefix[i] = len
            i += 1
        else:
            if len > 0:
                len = prefix[len-1]
            else:
                prefix[i] = len
                i += 1
    print(prefix)
    # 前缀1：A          0   prefix[0]=0     len=0
    # 前缀2：AB         0   needle[1] != needle[0] -> else -> else -> prefix[1]=0       len=0
    # 前缀3：ABC        0   needle[2] != needle[0] -> else -> else -> prefix[2]=0       len=0
    # 前缀4：ABCD       0   needle[3] != needle[0] -> else -> else -> prefix[3]=0       len=0
    # 前缀5：ABCDA      1   needle[4] == needle[0] -> prefix[4]=1                       len=1
    # 前缀6：ABCDAB     2   needle[5] != needle[1] -> prefix[5]=2                       len=2
    # 前缀6：ABCDABD    0   needle[6] != needle[0] -> len = prefix[2-1]=0 -> needle[6] != needle[0] -> else -> else -> prefix[6]=0
    # ABCDABD前缀表最长公共前后缀个数就为[0,0,0,0,1,2]


def move_prefix_table(prefix, n):
    # 前缀表移位
    for i in range(n-1, 0, -1):
        prefix[i] = prefix[i-1]
    prefix[0] = -1


if __name__ == '__main__':
    haystack = 'BBC ABCDAB ABCDABCDABDE '  # 主串
    needle = 'ABCDABD'  # 模式串

    n = len(needle)
    m = len(haystack)
    if n == 0:
        print(0)
    prefix = [0]*n  # 前缀表初始化

    prefix_table(needle, prefix, n)
    move_prefix_table(prefix, n)

    i, j = 0, 0
    while(i < m):
        if j == n-1 and haystack[i] == needle[j]:
            print(i-j)
            j = prefix[j]

        if haystack[i] == needle[j]:
            i += 1
            j += 1
        else:
            j = prefix[j]
            if j == -1:
                i += 1
                j += 1

"""
    ABCDABD的前缀:
    前缀1：A
    前缀2：AB
    前缀3：ABC
    前缀4：ABCD
    前缀5：ABCDA
    前缀6：ABCDAB
    后缀1：D
    后缀2：BD
    后缀3：ABD
    后缀4：DABD
    后缀5：CDABD
    后缀6：BCDABD
    
    最长公共前后缀的计算过程：（找子串前半段和后半段中重复子串的长度）
    前缀1：A          0
    前缀2：AB         0
    前缀3：ABC        0
    前缀4：ABCD       0
    前缀5：ABCDA      1
    前缀6：ABCDAB     2
    ABCDABD前缀表最长公共前后缀个数就为[0,0,0,0,1,2,0]
"""
